// 冒泡排序
function Bubble(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}
console.log(Bubble([1, 12, 4, 5, 6, 2]));

// 快速排序
function quickSort(arr) {
    if (arr.length < 2) return arr;
    let left = [],
        right = [];
    let mainIndex = Math.floor(arr.length / 2);
    let mainItem = arr.splice(mainIndex, 1)[0];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < mainItem) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([mainItem], quickSort(right));
}
console.log(quickSort([1, 12, 4, 5, 6, 2]));

// 插入排序
function insetSort(arr) {
    let temp;
    for (let i = 0; i < arr.length; i++) {
        let temp = arr[i];
        for (let j = i; j >= 0; j--) {
            if (arr[j - 1] > temp) {
                arr[j] = arr[j - 1];
            } else {
                arr[j] = temp;
                break;
            }
        }
    }
    return arr;
}
console.log(insetSort([1, 12, 4, 5, 6, 2]));

// 选择排序
function selectSort(arr) {
    let temp;
    for (let i = 0; i < arr.length; i++) {
        let index = i;
        temp = arr[i];
        for (let j = i; j < arr.length; j++) {
            if (arr[j] < temp) {
                index = j;
                temp = arr[j];
            }
        }
        [arr[index], arr[i]] = [arr[i], arr[index]];
    }
    return arr;
}
console.log(selectSort([1, 12, 4, 5, 6, 2]));

// 归并排序 先分再合
function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] > right[0]) {
            result.push(right.shift());
        } else {
            result.push(left.shift());
        }
    }
    return result.concat(left, right);
}

function mergeSort(arr) {
    if (arr.length < 2) return arr;
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

console.log(mergeSort([1, 12, 4, 5, 6, 2]));

// 希尔排序
function shellSort(arr) {
    let temp;
    for (let gap = Math.floor(arr.length); gap > 0; gap = Math.floor(gap / 2)) {
        for (let j = gap; j < arr.length; j++) {
            temp = arr[j];
            while (j - gap >= 0 && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j = j - gap;
            }
            arr[j] = temp;
        }
    }
    return arr;
}
console.log(shellSort([1, 12, 4, 5, 6, 2]));

// 计数排序
function countingSort(arr) {
    let max = Math.max(...arr);
    let min = Math.min(...arr);
    let newArr = [];
    for (let i = 0; i < arr.length; i++) {
        newArr[arr[i]] = newArr[arr[i]] + 1 || 1;
    }
    let index = 0;
    for (let i = min; i <= max; i++) {
        while (newArr[i] > 0) {
            arr[index++] = i;
            newArr[i]--;
        }
    }
    return arr;
}
console.log(countingSort([1, 12, 4, 5, 6, 2]));

// 基数排序
function radixSort(arr) {
    // mod 和 dev用于每次取出个位，十位百位上的数
    let counter = [],
        mod = 10,
        dev = 1;
    // 找出当前的数组中的最大值
    let max = Math.max(...arr);
    // 并且确定最大比较位数
    let maxDigit = 0;
    while (max != 0) {
        max = parseInt(max / 10);
        maxDigit++;
    }
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for (let j = 0; j < arr.length; j++) {
            let bucket = parseInt((arr[j] % mod) / dev);
            if (counter[bucket] == null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        let pos = 0;
        for (let j = 0; j < counter.length; j++) {
            let value = null;
            if (counter[j] != null) {
                while ((value = counter[j].shift()) != null) {
                    arr[pos++] = value;
                }
            }
        }
    }
    return arr;
}

console.log(radixSort([1, 12, 4, 5, 6, 2]));
